def solve():
n=int(input())
nums=list(map(int,input().split()))
ans = n * (n * 2 + 1)
visited = [0] * n
path = []
pt = 0
flag = False
while not visited[pt]:
path.append(pt)
visited[pt] = 1
pt += nums[pt]
if not 0 <= pt < n:
break
else:
ans -= (n - sum(visited)) * (2 * n + 1); flag = True
cnt = sum(visited)
if flag:
ans -= cnt * cnt
else:
ans -= (1 + cnt) * cnt // 2
new_visited = [0] * n
note = visited[:]
for i in range(n):
if not note[i]:
tmp = []
f = False
while not note[i]:
tmp.append(i)
note[i] = 1
i += nums[i]
if not 0 <= i < n: break
if (note[i] and new_visited[i] >= 0) or visited[i]: f = True
if f:
if new_visited[i]:
i = new_visited[i] - 1
for x in tmp:
new_visited[x] = i + 1
else:
for x in tmp:
new_visited[x] = -1
path_note = {v: i for i, v in enumerate(path)}
for i in range(n):
if not visited[i]:
if new_visited[i] != -1:
if visited[new_visited[i] - 1] == 0 or flag:
ans -= cnt
else:
ans -= cnt - path_note[new_visited[i] - 1]
print(ans)
for _ in range(int(input())):
solve()#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define sz(s) (int)s.size()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9 + 7;
const int N = 300300;
int n, a[N], col[N], cnt_col[N];
bool was[N], init_good;
ll ans;
bool used[N];
void f(int v) {
if (col[v] != -1)
return;
if (was[v]) {
col[v] = v;
return;
}
if (used[v]) {
col[v] = v;
return;
}
used[v] = 1;
int u = v + a[v];
if (u < 1 || u > n)
col[v] = 0;
else {
f(u);
col[v] = col[u];
}
}
void solve() {
ans = 0;
init_good = false;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
was[i] = 0;
{
int v = 1;
while (true) {
was[v] = 1;
v += a[v];
if (v < 1 || v > n) {
init_good = 1;
break;
}
if (was[v])
break;
}
}
for (int i = 1; i <= n; i++)
col[i] = -1, used[i] = 0;
for (int i = 1; i <= n; i++)
f(i);
for (int i = 0; i <= n; i++)
cnt_col[i] = 0;
for (int i = 1; i <= n; i++)
cnt_col[col[i]]++;
{
ll s = cnt_col[0];
if (init_good) {
for (int i = 1; i <= n; i++)
if (was[i])
s += cnt_col[i];
}
for (int i = 1; i <= n; i++)
was[i] = 0;
int v = 1;
while (true) {
if (init_good)
s -= cnt_col[v];
ans += s;
ans += n + 1;
was[v] = 1;
v += a[v];
if (v < 1 || v > n || was[v])
break;
}
for (int i = 1; i <= n; i++)
if (!was[i] && init_good)
ans += n + n + 1;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) solve();
return 0;
}232. Implement Queue using Stacks | 844. Backspace String Compare |
20. Valid Parentheses | 746. Min Cost Climbing Stairs |
392. Is Subsequence | 70. Climbing Stairs |
53. Maximum Subarray | 1527A. And Then There Were K |
1689. Partitioning Into Minimum Number Of Deci-Binary Numbers | 318. Maximum Product of Word Lengths |
448. Find All Numbers Disappeared in an Array | 1155. Number of Dice Rolls With Target Sum |
415. Add Strings | 22. Generate Parentheses |
13. Roman to Integer | 2. Add Two Numbers |
515. Find Largest Value in Each Tree Row | 345. Reverse Vowels of a String |
628. Maximum Product of Three Numbers | 1526A - Mean Inequality |
1526B - I Hate 1111 | 1881. Maximum Value after Insertion |
237. Delete Node in a Linked List | 27. Remove Element |
39. Combination Sum | 378. Kth Smallest Element in a Sorted Matrix |
162. Find Peak Element | 1529A - Eshag Loves Big Arrays |
19. Remove Nth Node From End of List | 925. Long Pressed Name |